/*
 * lab2.c
 *
 *  Created on: Jul 31, 2012
 *      Author: lakshman
 */

// DFS for directed graphs
// BPW, 4/2003

#include <stdio.h>
#include <stdlib.h>

#define WHITE 0
#define GRAY 1
#define BLACK 2

#define TREE 0
#define BACK 1
#define CROSS 2
#define FORWARD 3

int n; // number of nodes
int e; // number of edges
struct edge {
    int tail, head, type,capacity;
};
typedef struct edge edgeType;
edgeType *edgeTab;
int *firstEdge; // Table indicating first in range of edges with a common tail

int *discovery, *finish, *predecessor, *vertexStatus;
FILE *file;

struct stack {
    edgeType *edge;
    struct stack *next;
};

int stack_count=0,back_edge_count=0;
typedef struct stack stackEdgeType;
stackEdgeType *head=NULL;
stackEdgeType *cycleEdges_head=NULL;
stackEdgeType *cycleEdges_last=NULL;

//declaring pop function as it's return type is poiner
stackEdgeType* pop();
stackEdgeType* find_small_flow_in_cycle();

// Reading the input file and organize adjacency lists

int tailThenHead(const void* xin, const void* yin)
// Used in calls to qsort() and bsearch() for read_input_file()
{
    int result;
    edgeType *x, *y;

    x = (edgeType*) xin;
    y = (edgeType*) yin;
    result = x->tail - y->tail;
    if (result != 0)
        return result;
    else
        return x->head - y->head;
}

void read_input_file() {
    int a, b,c, i, j;
    edgeType work;
    edgeType *ptr;

    file = fopen("input.dat","r");
    printf("file %u",file);
    //scanf("%d %d", &n, &e);
    fscanf(file,"%d %d", &n, &e);
    edgeTab = (edgeType*) malloc(e * sizeof(edgeType));
    if (!edgeTab) {
        printf("edgeTab malloc failed %d\n", __LINE__);
        exit(0);
    }

    for (i = 0; i < e; i++) {
        //scanf("%d %d %d", &a, &b,&c);
        fscanf(file,"%d %d %d", &a, &b,&c);
        if (a < 0 || a >= n || b < 0 || b >= n) {
            printf("Invalid input %d %d at %d\n", a, b, __LINE__);
            exit(0);
        }
        edgeTab[i].tail = a;
        edgeTab[i].head = b;
        edgeTab[i].capacity = c;
    }

// sort edges
    qsort(edgeTab, e, sizeof(edgeType), tailThenHead);

// Coalesce duplicates into a single edge
    j = 0;
    for (i = 1; i < e; i++)
        if (edgeTab[j].tail == edgeTab[i].tail
                && edgeTab[j].head == edgeTab[i].head)
            ;
        else {
            j++;
            edgeTab[j].tail = edgeTab[i].tail;
            edgeTab[j].head = edgeTab[i].head;
        }
    e = j + 1;

// For each vertex as a tail, determine first in range of edgeTab entries
    firstEdge = (int*) malloc((n + 1) * sizeof(int));
    if (!firstEdge) {
        printf("malloc failed %d\n", __LINE__);
        exit(0);
    }
    j = 0;
    for (i = 0; i < n; i++) {
        firstEdge[i] = j;
        //printf("firstEdge[%d]=%d",i,j);
        //printf("node %d  start from %d",i,firstEdge[i]);
        for (; j < e && edgeTab[j].tail == i; j++)
            ;
    }
    firstEdge[n] = e;
    fclose(file);
}


int path_length=0;
int find_S_T_path_bkp(int s, int t) {

    int i,j,v,u,c;

    vertexStatus[s]=GRAY;
    for(i=firstEdge[s]; i<firstEdge[s+1]&& v!=t; i++) {
        v=edgeTab[i].head;
        c=edgeTab[i].capacity;
        //printf("\nvisiting edge %d %d %d\n",edgeTab[i].tail,edgeTab[i].head,edgeTab[i].capacity);
        if(vertexStatus[v]==WHITE && edgeTab[i].capacity>0) {
            vertexStatus[v]=GRAY;
            // printf("\nentering edge %d %d %d\n",edgeTab[i].tail,edgeTab[i].head,edgeTab[i].capacity);
            stackEdgeType  *elem= (stackEdgeType*)malloc(sizeof(stackEdgeType));
            elem->edge=&edgeTab[i];
            elem->next=NULL;
            push(elem);
            path_length++;
            //printf("found node %d %d",v,vertexStatus[v]);
            find_S_T_path_bkp(v,t);
        }
    }
    if(v==t)
    {
        printf("\npath found with length %d",path_length);
        show_stack();
        return 1;
    }
    else {
        path_length--;
        //printf("poping one level up");
        stackEdgeType *ele =pop();
        if(ele==NULL) {
            //printf("\npath not found");
            return 0;
        }
    }
}

int find_S_T_path(int s, int t) {
    int path_length=0;
    int i,u=s,v=0,c;
    vertexStatus[s]=GRAY;

    while(1) {
	i=firstEdge[u];
        //while(i<firstEdge[v+1] && v!=t){
        for(; i<firstEdge[u+1] && u!=t;) {
	    v=edgeTab[i].head;
            c=edgeTab[i].capacity;
            //printf("node %d color %d ",v,vertexStatus[v]);
	    //printf(" entering %d %d %d %d %d ",i,edgeTab[i].tail,edgeTab[i].head,edgeTab[i].capacity,vertexStatus[v]);
            if( vertexStatus[v]==WHITE && edgeTab[i].capacity>0) {
	      //if(edgeTab[i].capacity>0) {
	      vertexStatus[v]=GRAY;
	      //printf(" visiting edge %d %d %d %d %d ",i,edgeTab[i].tail,edgeTab[i].head,edgeTab[i].capacity,vertexStatus[v]);
              //printf("\n\t entering edge %d %d %d\n",edgeTab[i].tail,edgeTab[i].head,edgeTab[i].capacity);
              stackEdgeType  *elem= (stackEdgeType*)malloc(sizeof(stackEdgeType));
              elem->edge=&edgeTab[i];
              elem->next=NULL;
              push(elem);
              path_length++;
              //v=u;
              i=firstEdge[v];
              u=v;
              //printf("v = %d i=%d",v,i);
            }
            else {
	      i++;
            }
        }
        if(v==t) {
           // printf("\nfoudn S-T path %d %d \n",s,t);
            //find_smallest_path_reduce();
            //show_stack();
            return 1;
        }
        else {
            path_length--;
            //printf("poping one level up");
            stackEdgeType *ele =pop();
            if(ele!=NULL) {
                u=ele->edge->tail;
                //printf("poping one level up to node: %d \n",u);
            }
            else {
                //printf("\npath not found from %d %d",s,t);
                return 0;
            }
        }
    }
}

void find_all_S_T_pahts(int s, int t) {
    int res;
    do {
        clear_vertex_status();
        res=find_S_T_path(s,t);
        if(res)
            find_smallest_path_reduce();
    } while(res);
}

void clear_vertex_status() {
    int u;
    head=NULL;
    //cycleEdges=NULL;
    for (u = 0; u < n; u++) {
        vertexStatus[u] = WHITE;
    }
}


int time; /*Keeps node numbering*/
void DFS_graph_construct(int u)
{
    int i, v,c;

    if(vertexStatus[u]==WHITE) {
        discovery[u] = time;
    }
    time++;
    vertexStatus[u] = GRAY;
    //create an element for each edge to push it to the stack
    for (i = firstEdge[u]; i < firstEdge[u + 1]; i++) {
        stackEdgeType  *elem= (stackEdgeType*)malloc(sizeof(stackEdgeType));
        elem->edge=&edgeTab[i];
        elem->next=NULL;
        v = edgeTab[i].head;
        c=edgeTab[i].capacity;
        //printf("\nvisiting edge %d %d %d %d",edgeTab[i].tail, edgeTab[i].head,edgeTab[i].capacity,vertexStatus[v]);
        if (vertexStatus[v] == WHITE ) {
            //printf("\nedge is white");
            edgeTab[i].type = TREE;
            predecessor[v] = u;
            //add_to_cycle_edge(elem);
            DFS_graph_construct(v);
        } else if (vertexStatus[v] == GRAY) {
            //printf("\nedge is black");
            if(edgeTab[i].type !=BACK) {
                edgeTab[i].type =BACK;
                add_to_cycle_edge(elem);
            }
        }
        else if (discovery[u] < discovery[v]) {
            edgeTab[i].type = FORWARD;
            //printf("\nedge is black");
            predecessor[v] = u;
            //add_to_cycle_edge(elem);
            DFS_graph_construct(v);

        }
        else {
            //printf("\ncheckign edge for black");
            if(edgeTab[i].type !=BACK) {
                edgeTab[i].type =BACK;
                add_to_cycle_edge(elem);
            }
        }
    }
    //printf("\nsetting vertexStatus[%d] = BLACK",u);
    vertexStatus[u] = BLACK;
    time++;
    finish[u] = time;
}


void removeCycle() {
    stackEdgeType *temp= cycleEdges_head;
    int res;
    //printf("\n no of back edges is %d",back_edge_count);
    while(temp!=NULL) {
        int s=temp->edge->head;
        int t=temp->edge->tail;
        do {
            res=0;
            clear_vertex_status();
	    //printf("\n back edge capacity %d",temp->edge->capacity);
	    //printf("\n canceling smallest flow allong all edges in cycle (%d,%d, %d)\n",s,t,temp->edge->capacity);
            if(temp->edge->capacity>0){
                res =find_S_T_path(s,t);
	    }
            if(res==1) {
	      //printf("find path return for edge %d %d is %d",s,t,res);
	      stackEdgeType *back_edge = (stackEdgeType*) malloc(sizeof(stackEdgeType));
              back_edge->edge=temp->edge;
              back_edge->next=NULL;
              push(back_edge);
              find_smallest_cycle_reduce();
            }
        }
        while(res);
        temp=temp->next;
    }
}


void DFSvisit(int u) {
    int i, v,c;

    vertexStatus[u] = GRAY;
    time++;
    discovery[u] = time;
    //create an element for each edge to push it to the stack
    for (i = firstEdge[u]; i < firstEdge[u + 1]; i++) {
        stackEdgeType  *elem= (stackEdgeType*)malloc(sizeof(stackEdgeType));
        elem->edge=&edgeTab[i];
        elem->next=NULL;
        v = edgeTab[i].head;
        c=edgeTab[i].capacity;
        if (vertexStatus[v] == WHITE && c>0) {
            edgeTab[i].type = TREE;
            predecessor[v] = u;
            push(elem);
            DFSvisit(v);
        } else if (vertexStatus[v] == GRAY) {
            push(elem);
            edgeTab[i].type = BACK;
            show_stack();
            printf("\ncycle found poping cycle edges until edge starts with %d \n",v);
            stackEdgeType *ele=NULL;
            do {
                ele= pop();
                add_to_cycle_edge(ele);
            } while(ele->edge->tail!=v);
            find_smallest_cycle_reduce();
            removed_cycle_edges();
        }
        else if (discovery[u] < discovery[v])
            edgeTab[i].type = FORWARD;
        else
            edgeTab[i].type = CROSS;
    }
    vertexStatus[u] = BLACK;
    time++;
    finish[u] = time;
}



void push(stackEdgeType *elem) {
    stack_count++;
    if(head==NULL) {
        head=elem;
        head->next=NULL;
    }
    else {
        elem->next=head;
        head=elem;
    }
    //printf("\npushing edge :");
    //printf("%d %d %d \n" ,elem->edge->tail,elem->edge->head,elem->edge->capacity);

}

stackEdgeType* pop()
{
    stack_count--;
    if(head==NULL)
        return NULL;

    stackEdgeType *temp =head;
    // printf("\npoping edges :");
    //printf("%d %d %d\n" ,temp->edge->tail,temp->edge->head,temp->edge->capacity);
    head=head->next;
    temp->next=NULL;
    return temp;
}

void show_stack() {
    stackEdgeType *temp = head;
    printf("\n stack elements are \n");
    printf("\nt h c\n");
    while(temp!=NULL) {

        printf("%d %d %d  \n" ,temp->edge->tail,temp->edge->head,temp->edge->capacity);
        //printf("(%d<-%d)",temp->edge->head,temp->edge->tail);
        //if(temp->next!=NULL)
        //  printf(",");
        temp=temp->next;
    }

}

void find_smallest_cycle_reduce() {
    stackEdgeType *temp=head;
    stackEdgeType *min=temp;

    while(temp!=NULL) {
        if(temp->edge->capacity<min->edge->capacity) {
            min=temp;
        }
        temp=temp->next;
    }
    printf("\n Cancel cycle , limiting edge %d->%d has flow %d",min->edge->tail,min->edge->head,min->edge->capacity);
    temp=head;
    int min_cap=min->edge->capacity;
    while(temp!=NULL) {
        printf("\n%d->%d before flow %d ",temp->edge->tail,temp->edge->head,temp->edge->capacity);
        temp->edge->capacity-=min_cap;
        printf("after flow is %d \n",temp->edge->capacity);
        //printf("%d<-%d",temp->edge->head,temp->edge->tail);
        //if(temp->next!=NULL)
        //  printf("<-");
        //else
        //  printf(" flow : %d",min_cap);
        // printf("\n%d %d %d\n",temp->edge->tail,temp->edge->head,temp->edge->capacity);
        temp=temp->next;
    }
}

void add_to_cycle_edge(stackEdgeType *elem) {
    back_edge_count++;
    if(cycleEdges_head==NULL) {
        //printf("\nadding back edge (%d->%d, %d)\n" ,elem->edge->tail,elem->edge->head,elem->edge->capacity);
        cycleEdges_head=elem;
	cycleEdges_last=elem;
    }
    else {
        //printf("\nadding back edge (%d->%d, %d)\n" ,elem->edge->tail,elem->edge->head,elem->edge->capacity);
        //elem->next=cycleEdges;
        //cycleEdges=elem;
        cycleEdges_last->next=elem;
	cycleEdges_last=elem;
    }
    //printf("\nadded cycled edges : ");

}

void find_smallest_path_reduce() {

    stackEdgeType *temp=head;
    stackEdgeType *min=temp;

    while(temp!=NULL) {
        if(temp->edge->capacity<min->edge->capacity) {
            min=temp;
        }
        temp=temp->next;
    }
    //printf("\n reducing smallest flow in the path  %d between (%d,%d) \n",min->edge->capacity,min->edge->tail,min->edge->head);
    temp=head;
    int min_cap=min->edge->capacity;
    printf("\n");
    while(temp!=NULL) {
        //printf("\n%d->%d before flow %d ",temp->edge->tail,temp->edge->head,temp->edge->capacity);
        temp->edge->capacity-=min_cap;
        //printf("after flow is %d \n",temp->edge->capacity);
	if(temp->edge->capacity<=0)
	  printf("%d<=%d",temp->edge->head,temp->edge->tail);
	else
	  printf("%d<-%d",temp->edge->head,temp->edge->tail);
        if(temp->next!=NULL)
            printf("<-");
        else
            printf(" flow : %d",min_cap);
        // printf("\n%d %d %d\n",temp->edge->tail,temp->edge->head,temp->edge->capacity);
        temp=temp->next;
    }
}

// void cancel_smallest_flow_in_cycle() {
//
//     stackEdgeType *min =find_smallest_flow_in_cycle();
//     stackEdgeType *temp=cycleEdges;
//
//     //printf("\nafter cancelign min flow in cycle, the edges in cycle are\n");
//
//     int min_cap=min->edge->capacity;
//     while(temp!=NULL) {
//         temp->edge->capacity-=min_cap;
//         //printf("\n(%d->%d, %d)\n",temp->edge->tail,temp->edge->head,temp->edge->capacity);
//         temp=temp->next;
//     }
// }


void removed_cycle_edges() {
    //printf("\n removed cycled edges are \n");
    while(cycleEdges_head!=NULL) {
        stackEdgeType *temp = cycleEdges_head;
        //printf("\n %d %d %d\n",temp->edge->tail,temp->edge->head,temp->edge->capacity);
        cycleEdges_head=cycleEdges_head->next;
        temp->next=NULL;
        push(temp);
    }

}



int main() {
    int u, i, j, k, nextDFS;

    read_input_file();
    discovery = (int*) malloc(n * sizeof(int));
    finish = (int*) malloc(n * sizeof(int));
    predecessor = (int*) malloc(n * sizeof(int));
    vertexStatus = (int*) malloc(n * sizeof(int));
    if (!discovery || !finish || !predecessor || !vertexStatus) {
        printf("malloc failed\n");
        exit(0);
    }
// DFS code
    for (u = 0; u < n; u++) {
        vertexStatus[u] = WHITE;
        predecessor[u] = (-1);

    }
    time = 0;
    for (u = 0; u < n; u++)
        if (vertexStatus[u] == WHITE)
            //DFSvisit(u);
            DFS_graph_construct(u);
    removeCycle();

    //find_S_T_path(0,n-1);
    find_all_S_T_pahts(0,n-1);
//Output code

    /*printf("Vertex  discovery    finish     predecessor\n");
    for (i = 0; i < n; i++)
    	printf(" %3d      %3d         %3d          %3d\n", i, discovery[i],
    			finish[i], predecessor[i]);
    */printf("\nEdge 	Tail 	Head 	capacity\n");
    for (i = 0; i < e; i++) {
    	printf(" %3d  %3d  %3d  %3d  ", i, edgeTab[i].tail, edgeTab[i].head,edgeTab[i].capacity);
    	switch (edgeTab[i].type) {
    	case TREE:
    		printf("tree\n");
    		break;
    	case BACK:
    		printf("back\n");
    		break;
    	case CROSS:
    		printf("cross\n");
    		break;
    	case FORWARD:
    		printf("forward\n");
    		break;
    	}
    }

    free(edgeTab);
    free(firstEdge);
    free(discovery);
    free(finish);
    free(predecessor);
    free(vertexStatus);
    free(head);
    return 0;
}

